package text111;

public class Solution14 {
	 public boolean isSubStructure(TreeNode A, TreeNode B) {
		 if(A == null || B == null) return false;// 当A或者B为null，则直接返回false
	        return dfs(A,B);
	    }
	    private boolean dfs(TreeNode A, TreeNode B){
	        // 如果 A == null, 即这个分支没有找到一个与B的根节点相同的节点，则返回false.
	        if(A == null) return false;
	        // 如果A中找到了一个与B的根节点相同的节点，则判断以该节点为根节点的A的子树是否包含B，注意是包含，不是相等
	        if(A.val == B.val && contain(A,B)) return true;
	        // 如果当前节点不与B的根节点相同，则继续搜寻
	        return dfs(A.left,B) || dfs(A.right,B);
	    }
	    private boolean contain(TreeNode root1, TreeNode root2){
	        // 由于是判断 树root1 是否包含 树root2，因此判断 root1 包含 root2 的递归终止条件是 root2 == null，root1 不一定为 null
	        if(root2 == null) return true;
	        // 当 root2 != null 时，如果 roo1 == null 或者节点值不相等，则 A不包含B
	        if(root1 == null || root1.val != root2.val) return false;
	        // 继续对比剩下的节点
	        return contain(root1.left,root2.left) && contain(root1.right,root2.right);

		
	}
}
